package com.tgy.cmp;

import com.common.sort.tools.Integers;
import com.tgy.Sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: tgy
 * @Date: 2020-10-16 10:32
 */
public class ShellSort<E> extends Sort<E> {

    @Override
    protected void sort() {

        List<Integer> steps = shellStep();

        for (Integer step : steps) {

            for (int i = 0; i < step; i++) {

                for (int j = i + step; j < elements.length; j += step) {


                    E e = elements[j];
                    int index = j;

                    for (int x = j - step; x >= 0; x -= step) {

                        if (compare(e,elements[x]) < 0) {

                            elements[x + step] = elements[x];
                            index = x;
                        }else {

                            break;
                        }
                    }

                    if (index != j) {

                       elements[index] = e;
                    }

                }
            }

        }

    }

    private List<Integer> shellStep() {

        ArrayList<Integer> steps = new ArrayList<>();

        int n = 1;

        do {
            steps.add(0,n);
            n = n << 1;
        }while (n < elements.length);

        return steps;
    }
}
